/* 
 * File:   pager.cpp
 * Author: Chen Liu
 * 
 * Created on September 21, 2012, 12:40 PM
 */
#include <stdlib.h>
#include "pager.h"

Pager::Pager() 
{
    pageNum = 0;
    frame_num = 0;
    pageFaults = 0;
    currentPosition = 0;
}

void Pager::Init(AlgType alg, int numFrames)
{
    pageNum = 0;
    algType = alg;
    frame_num = numFrames;
    pageFaults = 0;
    PageRecord tmpRecord;
    tmpRecord.pageNum = -1;
    tmpRecord.mark = 0;
    frames = vector<PageRecord> (numFrames, tmpRecord);
    currentPosition = 0;
    freeFrames = vector<int>(numFrames);
    for (int i=0; i<numFrames; i++) {
        freeFrames[i] = i;
    }
}

void Pager::SetPageRefs(const vector<int> &refs)
{
    pageRefs = refs;
}

void Pager::SetPageNum(int num)
{
    pageNum = num;
    pageMark = vector<int>(num, 0);
    if (algType == eLRU) {
        for (int i=0; i<num; i++)
        {
            pageMark[i] = i;
        }
    }
}

bool Pager::AccessPage(int PageNum)
{
    for (int i=0; i<frame_num; i++)
    {
        if (frames[i].pageNum == PageNum) {
            AlgType tmpType = algType;
            switch (tmpType) {
                case eLRU:
                {                  
                   for (int j=0; j<pageNum; j++) {
                       if (pageMark[j] == PageNum) {
                           pageMark.erase(pageMark.begin()+j);
                           pageMark.insert(pageMark.begin(), PageNum);
                           break;
                       }
                   }
                   break;
                }
                case eLFU:
                {
                    pageMark[PageNum] = pageMark[PageNum] + 1;
                    break;
                }
                case eSecondChance:
                {
                    frames[i].mark = 1;
                    break;
                }
                default:
                    break;
            }
            currentPosition++;
            return true;
        }
    }
    AlgType tmpType = algType;
    switch (tmpType) {
        case eFIFO:
        {
            if (freeFrames.size()!=0) {
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[freeFrames[0]] = tmpRecord;
                freeFrames.erase(freeFrames.begin());
            }
            else {
                frames.erase(frames.begin());
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames.push_back(tmpRecord);
            }
            break;
        }
        case eRandom:
        {
            if (freeFrames.size()!=0) {
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[freeFrames[0]] = tmpRecord;
                freeFrames.erase(freeFrames.begin());
            } else {
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                int j = random() % frame_num;
                frames[j] = tmpRecord;
            }
            break;
        }
        case eLRU:
        {
            if (freeFrames.size()!=0) {
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[freeFrames[0]] = tmpRecord;
                freeFrames.erase(freeFrames.begin());
            } else {
                vector<int> markPosition(frame_num);
                for (int i=0; i<frame_num; i++) {
                    for (int j=0; j<pageNum; j++) {
                        if (pageMark[j] == frames[i].pageNum) {
                            markPosition[i] = j;
                        }
                    }
                }
                int max = 0, pos;
                for (int i=0; i<frame_num; i++)
                {
                    if (markPosition[i] > max) {
                        max = markPosition[i];
                        pos = i;
                    }
                }
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[pos] = tmpRecord;
            } 
            for (int i=0; i<pageNum; i++) {
                if (pageMark[i] == PageNum) {
                    pageMark.erase(pageMark.begin()+i);
                    pageMark.insert(pageMark.begin(), PageNum);
                    break;
                }
            }
            break;
        }
        case eLFU:
        {
            if (freeFrames.size() != 0) {
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[freeFrames[0]] = tmpRecord;
                freeFrames.erase(freeFrames.begin());
            } else {
                int minCount = INT_MAX;
                int pos;
                for (int i=0; i<frame_num; i++) {
                    if (pageMark[frames[i].pageNum] < minCount) {
                        minCount = pageMark[frames[i].pageNum];
                        pos = i;
                    }
                }
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[pos] = tmpRecord;
            }
            pageMark[PageNum] = pageMark[PageNum] + 1;
            break;
        }
        case eSecondChance:
        {
            if (freeFrames.size() !=0 ) {
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 1;
                frames[freeFrames[0]] = tmpRecord;
                freeFrames.erase(freeFrames.begin());
            } else {
                while ((*frames.begin()).mark) {
                    int tmp = frames[0].pageNum;
                    frames.erase(frames.begin());
                    PageRecord tmpRecord;
                    tmpRecord.pageNum = tmp;
                    tmpRecord.mark = 0;
                    frames.push_back(tmpRecord);
                }
                frames.erase(frames.begin());
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 1;
                frames.push_back(tmpRecord);
            }
            break;
        }
        case eOptimalPageReplacement:
        {
            if (freeFrames.size() !=0 ) {
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[freeFrames[0]] = tmpRecord;
                freeFrames.erase(freeFrames.begin());
            } else {
                
                vector<int> pos(frame_num, INT_MAX);
                for (int j=0; j<frame_num; j++) {
                    int i = currentPosition;
                    for (; i<(int)pageRefs.size(); i++) {
                        if (pageRefs[i] == frames[j].pageNum) {
                            pos[j] = i;
                            break;
                        }
                    }
                }
                int maxPos = 0;
                int rePos;
                for (int i=0; i<frame_num; i++) {
                    if (pos[i] > maxPos) {
                        maxPos = pos[i];
                        rePos = i;
                    }
                }
                PageRecord tmpRecord;
                tmpRecord.pageNum = PageNum;
                tmpRecord.mark = 0;
                frames[rePos] = tmpRecord;
            }
            currentPosition++;
            break;
        }
    }
    pageFaults ++;
    return false;
}

int Pager::GetPageFaults()
{
    return pageFaults;
}

